import collections
from typing import List


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        def player_move(x1, y1, x2, y2):
            """(x1,y1)=玩家位置;(x2,y2)=箱子位置"""
            visited3 = {(x1, y1)}
            queue2 = collections.deque([(x1, y1)])
            while queue2:
                x3, y3 = queue2.popleft()
                for x4, y4 in neighbors(x3, y3):
                    if (x4, y4) not in visited3:
                        if grid[x4][y4] != "#" and (x4, y4) != (x2, y2):
                            queue2.append((x4, y4))
                            visited3.add((x4, y4))
            return visited3

        # 寻找当前终点位置
        # 寻找当前箱子位置
        # 寻找当前玩家位置
        # 时间复杂度：O(M×N)
        target = (-1, -1)
        box = (-1, -1)
        player = (-1, -1)
        for i1 in range(m):
            for j1 in range(n):
                if grid[i1][j1] == "S":
                    player = (i1, j1)
                elif grid[i1][j1] == "B":
                    box = (i1, j1)
                elif grid[i1][j1] == "T":
                    target = (i1, j1)

        # 广度优先搜索：箱子位置+玩家位置（在箱子的哪一边）；每一次广度优先搜索寻找玩家能够到达的位置
        # 玩家在箱子位置：0=上方，1=右方，2=下方，3=左方
        visited1 = {}
        queue1 = collections.deque()

        # 计算初始位置：玩家可以到达箱子的哪一边
        visited2 = player_move(player[0], player[1], box[0], box[1])
        if (box[0], box[1] - 1) in visited2:  # 上方
            visited1[(box[0], box[1], 0)] = 0
            queue1.append((box[0], box[1], 0))
        if (box[0] + 1, box[1]) in visited2:  # 右方
            visited1[(box[0], box[1], 1)] = 0
            queue1.append((box[0], box[1], 1))
        if (box[0], box[1] + 1) in visited2:  # 下方
            visited1[(box[0], box[1], 2)] = 0
            queue1.append((box[0], box[1], 2))
        if (box[0] - 1, box[1]) in visited2:  # 左方
            visited1[(box[0], box[1], 3)] = 0
            queue1.append((box[0], box[1], 3))

        # 时间复杂度：O(M×N×4)×O(M×N)
        while queue1:
            for _ in range(len(queue1)):
                i1, j1, d = queue1.popleft()

                # 判断是否已经推到终点
                if (i1, j1) == target:
                    return visited1[(i1, j1, d)]

                v1 = visited1[(i1, j1, d)]

                # 计算玩家当前位置
                if d == 0:  # 上方
                    i2, j2 = i1, j1 - 1
                elif d == 1:  # 右方
                    i2, j2 = i1 + 1, j1
                elif d == 2:  # 下方
                    i2, j2 = i1, j1 + 1
                else:  # 左方
                    i2, j2 = i1 - 1, j1

                # 计算玩家能够到达的位置：(x1,y1)=玩家位置;(x2,y2)=箱子位置
                visited2 = player_move(i2, j2, i1, j1)

                # 尝试向上方推动箱子
                i3, j3 = i1, j1 - 1
                if j3 >= 0 and grid[i3][j3] != "#" and (i1, j1 + 1) in visited2:
                    if (i3, j3, 2) not in visited1:
                        visited1[(i3, j3, 2)] = v1 + 1
                        queue1.append((i3, j3, 2))
                # 尝试向右方推动箱子
                i3, j3 = i1 + 1, j1
                if i3 < m and grid[i3][j3] != "#" and (i1 - 1, j1) in visited2:
                    if (i3, j3, 3) not in visited1:
                        visited1[(i3, j3, 3)] = v1 + 1
                        queue1.append((i3, j3, 3))
                # 尝试向下方推动箱子
                i3, j3 = i1, j1 + 1
                if j3 < n and grid[i3][j3] != "#" and (i1, j1 - 1) in visited2:
                    if (i3, j3, 0) not in visited1:
                        visited1[(i3, j3, 0)] = v1 + 1
                        queue1.append((i3, j3, 0))
                # 尝试向左方推动箱子
                i3, j3 = i1 - 1, j1
                if i3 >= 0 and grid[i3][j3] != "#" and (i1 + 1, j1) in visited2:
                    if (i3, j3, 1) not in visited1:
                        visited1[(i3, j3, 1)] = v1 + 1
                    queue1.append((i3, j3, 1))

        # 没有办法推到目的地
        return -1


if __name__ == "__main__":
    # 3
    print(Solution().minPushBox(grid=[["#", "#", "#", "#", "#", "#"],
                                      ["#", "T", "#", "#", "#", "#"],
                                      ["#", ".", ".", "B", ".", "#"],
                                      ["#", ".", "#", "#", ".", "#"],
                                      ["#", ".", ".", ".", "S", "#"],
                                      ["#", "#", "#", "#", "#", "#"]]))

    # -1
    print(Solution().minPushBox(grid=[["#", "#", "#", "#", "#", "#"],
                                      ["#", "T", "#", "#", "#", "#"],
                                      ["#", ".", ".", "B", ".", "#"],
                                      ["#", "#", "#", "#", ".", "#"],
                                      ["#", ".", ".", ".", "S", "#"],
                                      ["#", "#", "#", "#", "#", "#"]]))

    # 5
    print(Solution().minPushBox(grid=[["#", "#", "#", "#", "#", "#"],
                                      ["#", "T", ".", ".", "#", "#"],
                                      ["#", ".", "#", "B", ".", "#"],
                                      ["#", ".", ".", ".", ".", "#"],
                                      ["#", ".", ".", ".", "S", "#"],
                                      ["#", "#", "#", "#", "#", "#"]]))

    # -1
    print(Solution().minPushBox(grid=[["#", "#", "#", "#", "#", "#", "#"],
                                      ["#", "S", "#", ".", "B", "T", "#"],
                                      ["#", "#", "#", "#", "#", "#", "#"]]))

    # 测试用例4/18 : 7
    print(Solution().minPushBox(grid=[["#", ".", ".", "#", "#", "#", "#", "#"],
                                      ["#", ".", ".", "T", "#", ".", ".", "#"],
                                      ["#", ".", ".", ".", "#", "B", ".", "#"],
                                      ["#", ".", ".", ".", ".", ".", ".", "#"],
                                      ["#", ".", ".", ".", "#", ".", "S", "#"],
                                      ["#", ".", ".", "#", "#", "#", "#", "#"]]))

    # 测试用例12/18 :
    print(Solution().minPushBox(grid=
                                [[".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", "#", "#", ".", "B", ".", ".", ".", ".", "."],
                                 [".", ".", ".", "#", ".", ".", ".", ".", "#", "#", ".", "."],
                                 [".", ".", "#", ".", ".", ".", ".", ".", ".", ".", ".", "."],
                                 ["#", ".", "#", ".", ".", ".", ".", ".", ".", ".", "#", "."],
                                 [".", ".", ".", ".", ".", ".", ".", ".", "S", ".", "T", "#"],
                                 [".", "#", ".", ".", ".", "#", ".", ".", ".", ".", ".", "#"],
                                 ["#", ".", ".", ".", ".", "#", ".", ".", "#", ".", ".", "."],
                                 ["#", ".", ".", "#", "#", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", "#", ".", "#", ".", ".", ".", "#", "."],
                                 [".", ".", "#", ".", "#", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "#"]]))
